HEAPSORT(A, n)
BUILD-MAX-HEAP(A, n)
for i ? n downto 2
do exchange A[1] ? A[i ]
MAX-HEAPIFY(A, 1, i ? 1)



BUILD-MAX-HEAP(A, n)
for i ?	n/2
 downto 1
do MAX-HEAPIFY(A, i, n)



MAX-HEAPIFY(A, i, n)
l ? LEFT(i )
r ? RIGHT(i )
if l ? n and A[l] > A[i ]
then largest ?l
else largest ?i
if r ? n and A[r ] > A[largest]
then largest ?r
if largest = i
then exchange A[i ] ? A[largest]
MAX-HEAPIFY(A, largest, n)